Computability

Computability is a complex issue in Computer Science. There are tasks that are simply not computable - meaning that we cannot write a program to solve the problem. It is not that computer scientists have not yet discovered how to write an algorithm for such a program but rather that there simply is no algorithm. An example of this is the 'halting problem'. It can be demonstrated (See "Discrete Mathematics in Computer Science", page 52) that it is not possible to write a program that can decide if another program will always halt.

There are other tasks that, while theoretically computable, require so much time that they might as well be non computable. There exists a whole class of problems that are like this. The classic example is the 'Traveling Salesperson' problem:

For small numbers of cities this problem is easy but it turns out that as the number of cities grows, the time required to solve the problem grows much faster. In fact, the time grows so much faster that for relatively small numbers of cities (say 50), the time required to determine the shortest path can be counted in centuries.

People reading this immediately reply by saying that all we need is a faster computer. However, that is not the solution for problems like the traveling salesperson. Yes, we may get a computer that solves this problem for 50 cities but, because the time grows so fast as we add a few cities, this faster computer will still require centuries to solve the problem for 60 or 70 cities. In other words, there is no algorithm that solves the 'general problem' in a reasonable amount of time.

A complete discussion of computability is really beyond the scope of this text. However, hopefully this short introduction has given you, the reader, some sense of the problem.